package study.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序
 */
public class SortDemo {
    static int cmpCount = 0;
    static int swapCount = 0;
    static int sortCount = 0;
    public static void main(String[] args) {
        Sortable[] sortables = new Sortable[]{
                new BubbleSort(),
                new InsertSort(),
                new SelectSort()
        };

        int[] arr = build(10);
        System.out.print("原数组：");
        print(arr);
        for (Sortable sortable : sortables) {
            int[] copy = Arrays.copyOf(arr, arr.length);

            System.out.println(sortable);
            sortCount = 0;
            cmpCount = 0;
            swapCount = 0;
            sortable.sort(copy);
            System.out.print("排序后：");
            print(copy);
            System.out.println("排序次数 -> " + sortCount);
            System.out.println("比较次数 -> " + cmpCount);
            System.out.println("交换次数 -> " + swapCount);
            System.out.println();
            System.out.println();
        }


    }

    static int[] build(int length) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(10000);
        }
        return arr;
    }

    static void print(int arr[]) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    private interface Sortable {
        void sort(int[] arr);
    }

    private static class BubbleSort implements Sortable {
        @Override
        public String toString() { return "-------- BubbleSort ----------"; }

        @Override
        public void sort(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                boolean flag = true; // 退出标识
                for (int j = arr.length - 1; j > i; j --) {
                    if(cmp(arr, j, j - 1) < 0) {
                        swap(arr, j, j - 1);
                        flag = false;
                    }
                }
//                System.out.printf("第%d次，排序后：", i + 1);
//                print(arr);
                sortCount ++;
                if(flag)
                    return;
            }
        }
    }

    private static class SelectSort implements Sortable {
        @Override
        public String toString() { return "-------- SelectSort ----------"; }
        @Override
        public void sort(int[] arr) {
            final int l = arr.length;
            for (int i = 0; i < l; i++) {
                int minIndex = i;
                for (int j = i + 1; j < l; j++) { // 找到最小值的索引
                    if(cmp(arr, j, minIndex) < 0)
                        minIndex = j;
                }
                if(minIndex != i) {
                    swap(arr, minIndex, i);
                }
//                System.out.print("排序一次后：");
//                print(arr);
                sortCount ++;
            }
        }
    }

    private static class InsertSort implements Sortable {
        @Override
        public String toString() { return "-------- InsertSort ----------"; }
        @Override
        public void sort(int[] arr) {
            final int l = arr.length - 1;
            int insertIndex = 0;
            int lastInsertValue = arr[0];
            for (int i = 0; i < l; i++) {
                if(cmp(arr, i, i + 1) > 0) {// 前面的元素比后面大，插入
                    int t = arr[i + 1];
                    for (int j = (t >= lastInsertValue) ? insertIndex : 0; j <= i + 1; j++) { // 找到要插入的位置
                        if(cmp(arr,i + 1,j) < 0) {
                            insertIndex = j;
                            break;
                        }
                    }
                    for (int j = i + 1; j > insertIndex; j--) { // 元素往后移动
                        arr[j] = arr[j - 1];
                        swapCount ++;
                    }
                    arr[insertIndex] = t; // 插入
                    lastInsertValue = t;
//                    System.out.print("排序一次后：");
//                    print(arr);
                    sortCount ++;
                }
            }
        }
    }


    static void swap(int[] arr, int i1, int i2) {
        swapCount ++;
        int t = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = t;
    }

    static int cmp(int[] arr, int i1, int i2) {
        cmpCount++;
        return Integer.compare(arr[i1], arr[i2]);
    }
}
